As communications have progressed into the electronic domain, information has become easy to copy and disseminate. The prevalence of electronic communication has made for many productivity advances, and an increase in knowledge and information sharing. However, due to the ease of dissemination, there is an ever increasing need for privacy and authentication in electronic communications.
To retain privacy, the method of encrypting data using a key is very well known. In a symmetric key cryptographic protocol, correspondents share a common secret key. This key must be agreed upon by the parties, with its secrecy maintained throughout the conversation.
Public key cryptographic protocols were first proposed in 1976 by Diffie-Hellman. A public-private key pair is created for each correspondent, with the public key made available to other parties, and the private key information kept to the recipient. Any message encrypted using the public key of a recipient can only be decrypted using the private key of that same recipient. The private key cannot be derived from the knowledge of the plaintext, ciphertext and public key.
Public key protocols may be used to establish a common key that is shared by a pair of correspondents. Once the common key is established, it may be used to exchange information using a symmetric key protocol.
Key establishment is the process by which two (or more) parties establish a shared secret key, called the session key. In key agreement protocols, both parties contribute information which jointly establishes the shared secret key. The number of message exchanges required to establish the shared secret key is known as the number of passes.
A key establishment protocol is said to provide key authentication if one party is assured that no other party aside from the intended second party may learn the value of the session key. Sometimes this property is called implicit key authentication.
A key establishment protocol is said to provide key confirmation if one party is assured that a specifically identified second party actually has possession of the particular session key.
Key agreement protocols are generally based on hard problems. These problems can be formulated quickly, but do not have efficient solution algorithms. Problems such as the discrete logarithm problem and integer factorization fall into this category.
However, advances in science and technology have made computing increasingly efficient and powerful. In response, argument complexity is constantly increasing to make attempts at solving cryptographic problems even more difficult. Key agreement protocols have also increasingly relied on longer private keys, making key agreement and authentication much slower and more computationally intensive.
One of the most commonly known methods of key agreement and confirmation is Diffie-Hellman Key Agreement Protocol with Key Confirmation (the Diffie-Hellman protocol). This method allows two parties to combine information to establish a shared secret for the duration of a session. The Diffie-Hellman protocol can be implemented practically in any group in which both the discrete logarithm problem is hard and the group operation is efficient. One example of such a group is the elliptic curve cyclic group defined over the finite field Fp composed of integers from 0 to p-1, where p is a prime number. The group elements are points lying on a defined elliptic curve and having coordinates that are elements of the underlying field. An elliptic curve group typically utilises an additive notation so that a k-fold group operation of a point P requires addition of the point k times and is written kP. A cryptosystem implemented using an elliptic curve group is known as an elliptic curve cryptosystem, ECC. Other groups commonly used are multiplicative groups, such as the non-zero integers in Fp, where p is a prime number, and the corresponding k-fold group operation is denoted αk, where α is a generator of the group.
The Diffie-Hellman protocol with key confirmation performed in an ECC requires an elliptic curve cyclic group E of order n with generating point G and identity element 0. Key establishment requires exchange of messages, while the key confirmation requires an additional set of message exchanges. Protocol messages are sent between an initiating correspondent A and a responding correspondent B as below:
a) A→B: X:=xG:
b) A←B: Y:=yG;
c) A←B: MACKB(Y, X, IDB);
d) A→B: MACKA(X, Y, IDA);
First, A selects a (secret) random integer x ε [1, n-1], and B selects a (secret) random integer y ε [1, n-1]. These secret integers are ephemeral private keys for each party. Once these integers have been selected, the ephemeral public key X:=xG is sent from A to B, and the ephemeral public key Y:=yG is sent from B to A. A shared secret for the session is then established for the two parties as a combination of the public key received from the other party and its own private ephemeral key. For party A, the shared secret is computed as KA:=xY=xyG, and for party B, the shared secret is computed as KB:=yX=yxG. Once the secret is agreed upon, the keys are authenticated using a Message Authentication Code (MAC), as is well known in the art. The Message Authentication Code MACKB(Y, X, B) is generated by B and MACKA(X, Y, A) is generated by A (where MACKB, and MACK:4, are keyed MAC algorithms well known in the art). These two MAC's are then exchanged between the parties to confirm that the identical shared secret keys have been calculated.
The shared secret may then be used directly as the key for symmetric key protocol, or, more usually, is used as an input to a key derivation function (KDF) from which the session key is derived, which is subsequently used with a symmetric-key based cryptographic scheme.
The ElGamal key agreement protocol is a one-pass variant on Diffie-Hellman key agreement. The setup is identical to the original Diffie-Hellman arrangement; however, the public key Y:=yG of B is assumed to have been authenticated and known to A a priori. A single protocol message is sent as below, which may be followed by a one-pass confirmation:
a) A→B: X:=xG;
b) A computes KA:=xY;
c) A→B: MACKA(X, Y, IDA);
As stated, A begins with an authenticated copy of B's public key, Y:=yG. A then generates its private key x ε [1, n-1] and sends its generated public corresponding key X:=xG to B. The two parties then possess the required information to generate the shared secret, as in the Diffie-Hellman process. For party A, the shared secret is again computed as KA:=xY=xyG, and for party B, the shared secret is again computed as KB:=yX 32 yxG.
These methods of key agreement and confirmation are quite secure, because from the publicly exchanged messages X:=xG and Y:=yG, it is difficult to recover the original private keys x and y, or the Diffie-Hellman key K=(xy)G. To increase security of the transmitted messages, the order n of the group E must be increased accordingly. However, the computation of the ephemeral or session keys X, Y have been slowed as a result, particularly in the multiplication of the generating point G, by increasingly large scalars x and y.
Another well-known method of key agreement and confirmation is the Menezes-Qu-Vanstone. (MQV) protocol, which is based on the Diffie-Hellman scheme. Elliptic curve finite groups can also be used in this protocol, resulting in the elliptic curve MQV protocol (ECMQV). In general, ECMQV allows parties to generate a shared key K that binds a static or long term public-private key pair with an ephemeral public-private key pair. This is in contrast to the Diffie-Hellman scheme, which only uses an ephemeral public-private key pair. An implicit signature quantity for each party is produced from the party's own private static and ephemeral keys, and the corresponding party's public static and ephemeral keys. The two implicit signatures are combined to produce a shared secret between the two parties. Since each party shares a key based on components including the other party's static key, the authenticity of the other party is implicitly verified, as long as the security of the static public-private pairs has not been compromised.
The ECMQV protocol provides numerous cryptographic advantages beyond the Diffie-Hellman scheme that are well known in the art. The setup is similar to Diffie-Hellman, but contains an additional static public-private key pair for the communicating parties. The correspondent A has a public-private static key pair (A,α), and the correspondent B has a public-private static key pair (B, b), where A:=αG and B:=bG. The parties A and B are usually assumed to possess αpriori the other party's public static key. As in the Diffie-Hellman scheme, an ephemeral public-private key pair (X, x) and (Y, y) are generated for the parties, where X:=xG and Y:=yG, and x ε [1, n-1] and y ε [1, n-1]. Once again, G is the generating point of the elliptic curve group. Protocol messages are sent as below:
a) A→B: X:=xG;
b) A←B: Y:=yG;
As in Diffie-Hellman, correspondent A selects an ephemeral private key x ε [1, n-1], and correspondent B selects an ephemeral private key y ε [1, n-1]. Once the ephemeral private keys have been selected, the ephemeral public key X:=xG is sent from correspondent A to correspondent B, and the ephemeral public key Y:=yG is sent from correspondent B to correspondent A. A shared secret is once again established for the two parties. However, this key is not only a combination of the message received (X or Y), and the ephemeral private key (x or y), but also includes the static public-private key pairs of the correspondents. For party A, the shared secret is computed as K=KA=SA(Y+ YB), where SA is the implicit signature of A defined as SA=(x+ Xa) mod n. For party B, the shared key is computed as K=KBSB(X+ XA), where SB is the implicit signature of A defined as SB=(y+ Yb) mod n. The terms X and Y are the non-zero scalars derived from ephemeral public keys X and Y by taking the first L bits of the first component of the point X and the point Y, respectively, and representing these as integers, where
  L  =            ⌈                        (                                    ⌊                                                log                  2                                ⁢                n                            ⌋                        +            1                    )                2            ⌉        .  
There is also a one-pass variant on the ECMQV key agreement protocol. As in ElGamal, party A has αpriori knowledge of the public key of party B. However, this time party A has possession of the public static key for B. The setup is similar to the ECMQV arrangement described above: however, private-public static key pair (α,A) for party A, and the ephemeral private-public key pair (y, Y) for party B are not used. A single protocol message is sent as below:
a) A→B: X:=xG;
This protocol assumes that party A begins with an authenticated copy of B′s public static key, B:=bG. Party A then generates its private session key x ε [1, n-1] and sends its public key X:=xG to party B. The two parties then possess the required information to generate the shared secret, similar to the ElGamal protocol. However, party B is implicitly authenticated on the basis of the public portion of static key pair (B, b). For party A, the shared key is computed as K=KA:=SA(B+ BB ), where SA:=(x+ Xα)mod n. For party B, the shared key is computed as K=KB:=SB(X+ XA), where SB:=(b+ Bb) mod n. Since party A contributes both ephemeral and static keys, implicit key authentication from party A to party B is provided (as also evidenced by the formula K=KB:=SB(X+ XA)). The equivalence of the shared secret for the two parties K=KA=KB can again be shown by the expansion of terms.
In each of the above protocols, computation of the shared secret requires the multiplication of a point by scalars, referred to a point multiplication. Point multiplication typically dominates the execution time of elliptic curve cryptosystems, and the execution time increases as the order n of the group E increases.